package _go

/*
199. 二叉树的右视图
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。



示例 1:



输入: [1,2,3,null,5,null,4]
输出: [1,3,4]
示例 2:

输入: [1,null,3]
输出: [1,3]
示例 3:

输入: []
输出: []*/

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rightSideView(root *TreeNode) []int {
	return bfs(root)
}

//思路 层序遍历 层序的第一个值打印出来就行 还可以用深度遍历  深度的一个值打印出来
func bfs(root *TreeNode) []int {
	if root == nil {
		return []int{}
	}
	res := []int{}
	bfsSlice := []*TreeNode{root}

	for len(bfsSlice) > 0 {
		tmp := bfsSlice
		bfsSlice = []*TreeNode{}
		for i := 0; i < len(tmp); i++ {
			if i == 0 {
				//只要一个节点
				res = append(res, tmp[i].Val)
			}
			//进行层序遍历 从右边开始遍历
			if tmp[i].Right != nil {
				bfsSlice = append(bfsSlice, tmp[i].Right)
			}
			if tmp[i].Left != nil {
				bfsSlice = append(bfsSlice, tmp[i].Left)
			}
		}
	}
	return res
}
